2020-05-22 18:04:32

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param Integer[] $preorder
     * @param Integer[] $inorder
     * @return TreeNode
     */
    function buildTree($preorder, $inorder) {
        $treeRoot = new TreeNode(null);
        $this->loop($treeRoot, $preorder, $inorder);
        return $treeRoot;
    }
    function loop($tree, $preorder, $inorder){
        $tree->val = $preorder[0];
        if(1 >= count($preorder)){
            return $tree;
        }
        $leftLen = array_search($preorder[0], $inorder);
        // $rightLen = count($inorder) - $leftLen - 1;
        //中序遍历 左
        $inorderLeft = array_slice($inorder, 0, $leftLen);
        //前序遍历 左
        $preorderLeft = array_slice($preorder, 1, $leftLen);;
        //中序遍历 右
        $inorderRight = array_slice($inorder, $leftLen + 1);
        //前序遍历 右
        $preorderRight = array_slice($preorder, $leftLen + 1);
        if(!empty($preorderLeft)){
            $treeLeft = new TreeNode(null);
            $tree->left = $this->loop($treeLeft, $preorderLeft, $inorderLeft);
        }
        if(!empty($preorderRight)){
            $treeRight = new TreeNode(null);
            $tree->right = $this->loop($treeRight, $preorderRight, $inorderRight);
        }
        return $tree;
    }
}

20201123

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        treeRoot = None
        if preorder:
            treeRoot = TreeNode(None)
            self.makeTree(treeRoot, preorder, inorder)
        return treeRoot
    
    def makeTree(self, node, preorder, inorder):
        node.val = preorder[0]
        if not preorder:
            node = None
            return
        #获得中序遍历的位置
        leftLen = inorder.index(preorder[0])
        #获取子节点数组段
        preorderLeft = preorder[1:leftLen + 1]
        preorderRight = preorder[leftLen + 1:]
        inorderLeft = inorder[0:leftLen]
        inorderRight = inorder[leftLen + 1:]

        if [] != preorderLeft:
            node.left = TreeNode(None)
            self.makeTree(node.left, preorderLeft, inorderLeft)
        if [] != preorderRight:
            node.right = TreeNode(None)
            self.makeTree(node.right, preorderRight, inorderRight)